/*
https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-rblsf/
 */
public class Solution138 {

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        if (head==null){
            return null;
        }
        Node temp=head;
        while (temp!=null){
            Node node=new Node(temp.val);
            node.next=temp.next;
            temp.next=node;
            temp=temp.next.next;
        }
        temp=head;
        while (temp!=null){
            Node t=temp.next;
            t.random=temp.random!=null?temp.random.next:null;
            temp=temp.next.next;
        }
        Node ans=head.next;
        temp=head;
        while (temp!=null){
            Node tempNode=temp.next;
            temp.next=temp.next.next;
            tempNode.next=temp.next!=null?temp.next.next:null;
            temp=temp.next;
        }
        return ans;
    }

    public static void main(String[] args) {
        Node node1=new Node(7);
        Node node2=new Node(13);
        Node node3=new Node(11);
        Node node4=new Node(10);
        Node node5=new Node(1);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node1.random=null;
        node2.random=node1;
        node3.random=node5;
        node4.random=node3;
        node5.random=node1;
        Node newNode=new Solution138().copyRandomList(node1);
        assert newNode!=node1;
        assert newNode.val==node1.val;
        assert newNode.next.val==node1.next.val;
    }
}
